/* *
*  核心思想是将待排序的序列按照位数划分为不同的数字位，然后分别对每位上的数字进行排序，最终得到有序序列
* 基数排序的时间复杂度为O(d(n+k))，其中d为数字位数，n为元素个数，k为每位数字的可能取值范围，空间复杂度为O(n+k) 稳定
* 基数排序的流程如下：
*  1.获取最高位数，对所有数字补充零使其长度达到最高位数；
*  2.按照个位数进行计数排序，并将结果存储在新的数组中；
*  3.按照十位数进行计数排序，并将结果存储在新的数组中；
*  4.重复步骤3，直到达到最高位数。
* */

function radixSort(arr) {
    //? 分桶
    const bucketList = Array.from({ length: 10 }, () => []);
    //? 浅拷贝一份
    const numberList = [...arr];
    //? 获取最高位数 如10就是两位
    let maxDigit = getMaxDigit(arr);
    //? 按照位数进行牌序 先低位数再高位数 这样高位数会放在数组的后面
    for (let i = 0; i < maxDigit; i++) {
        //? 将数字放入桶中
        for (let j = 0; j < numberList.length; j++) {

            const digit = getDigit(numberList[j], i);

            bucketList[digit].push(numberList[j]);
        }
        numberList.length = 0;
        //? 此时在某一位数上完成一轮，数组也加上了 需要放入结果数组了
        //? 比如有一个10和一堆个位数 那么在第一轮(个位轮次) 10会放在数组最前
        //? 而在第二轮(十位轮次) 10就会放到最后面了(10 / 10 % 10 === 1 而 7 / 10 % 10 === 0 故10会放在后面的箱子里 故在结果中也会在后面)
        for (let j = 0; j < bucketList.length; j++) {
            numberList.push(...bucketList[j]);
            bucketList[j] = [];
        }
    }
    return numberList;
}
//? 拿到最大位次
function getMaxDigit(arr) {
    let max = 0;
    for (let i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i].toString().length);
    }
    return max;
}
//? 拿到应该放入哪个箱子
function getDigit(num, i) {
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}



const arr = [5,2,6,1,7,2,10,8]
console.log(radixSort(arr));
